//求树的最大深度，也就是最大层数，根节点的深度为1
//可以用递归法或者迭代法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
#include <algorithm>
using std::max;
//递归法
//每次向下分别搜索左右结点，返回左右子树中深度最大的一个再加1，就是当前搜索节点的最大深度
//把根节点也按此方法搜索，最后就可以返回最大深度
/* 
int getDepth(TreeNode* node)
{
    if(!node) return 0;
    int leftside=getDepth(node->left);
    int rightside=getDepth(node->right);
    return 1+max(leftside,rightside);
}

int maxDepth_recursion(TreeNode* root)
{
    return getDepth(root);
}
*/
//简化版
int getDepth(TreeNode* node)
{
    if(!node) return 0;
    return 1+max(getDepth(node->left),getDepth(node->right));
}

int maxDepth_recursion(TreeNode* root)
{
    return getDepth(root);
}

//迭代法
//使用一个队列来实现，其实就相当于层序遍历，遍历的最大层数就是最大深度
#include <queue>
using std::queue;
int maxDepth_queue(TreeNode* root)
{
    if(!root) return 0;
    queue<TreeNode*> que;
    int depth=0;
    que.push(root);
    while(!que.empty()){
        depth++;
        int size=que.size();
        for(int i=0;i<size;i++){
        TreeNode* node=que.front();
        que.pop();
        if(node->left) que.push(node->left);
        if(node->right) que.push(node->right);//if判断必不可少
        }
    }
    return depth;
}